#include <string>

#define PAGESIZE    16384   // 16KB
// 16-bit addr  +  16-bit size
typedef int RecordID;

typedef struct pagemgr_t {
    unsigned short total_size;      // total size of active record data
    unsigned short num_records;     // number of valid records
    unsigned short del_first;       // indices of deleted records
    unsigned short addr_offset;     // total size of address pointers
    unsigned short record_offset;   // last byte of allocated record data
    const char page[PAGESIZE];      // Page memory
} pagemgr_t;

pagemgr_t pagemgr;

// called at the beginning of the program
void init() {
    memset(&pagemgr, 0, sizeof(pagemgr));
    pagemgr.del_first = 0xffff;
}

static unsigned int getaddr(unsigned short ridx)
{
    if (ridx<<2 + 4 > PAGESIZE) // invalid idx
        return;
    unsigned int *p = pagemgr.page + PAGESIZE - (ridx+1)*4;
    return *p;
}

static void setaddr(unsigned short ridx, unsigned int value)
{
    if (ridx<<2 + 4 > PAGESIZE) // invalid idx
        return;
    unsigned int *p = pagemgr.page + PAGESIZE - (ridx+1)*4;
    *p = value;
}

static void defrag_records()
{
    unsigned int addr, n = 0;
    unsigned short ridx, offset, dest_offset;
    char *page_dup = new char[PAGESIZE];

    // dup the entire page
    memcpy(page_dup, pagemgr.page, PAGESIZE);

    offset = dest_offset = ridx = 0;
    while (n < pagemgr.num_records) {
        addr = getaddr(ridx);
        size = addr & 0x0000ffff;
        offset = addr >> 16;
        if (offset > 0 && offset + size < PAGESIZE) {
            // valid record
            memcpy(pagemgr.page + dest_offset,
                   page_dup + offset, size);
            
            // update the address table with new addr
            addr = dest_offset << 16 + size;
            setaddr(ridx, addr);

            dest_offset += size;
            n++;
        }
        ridx++;
    }

    pagemgr.record_offset = dest_offset;
    delete page_dup [];
}

RecordID AddRecord(string r)
{
    RecordID id;
    unsigned short offset;
    int size = r.size();
    record_hdr_t *prev_hdr, *cur_hdr;
    
    if (size <= 0 || size > PAGESIZE) return -1;

    // indeed run out of space
    if (pagemgr.total_size + size > PAGESIZE - pagemgr.addr_offset) {
        return -1;
    }
    
    // tail of the record list
    if (pagemgr.record_offset + pagemgr.addr_offset + size > PAGESIZE) {
        // compress free space to insert new record
        defrag_records();
    }

    unsigned short ridx;
    // find an empty slot in addr table or increase table size
    if (pagemgr.del_first != 0xffff &&
        (pagemgr.del_first+1)*4 < pagemgr.addr_offset)
    {
        ridx = pagemgr.del_first;
        pagemgr.del_first = getaddr(pagemgr.del_first) & ~(1<<31);
    } else {
        // increase addr table
        pagemgr.addr_offset += 4;
        ridx = pagemgr.add_offset/4 - 1;
        pagemgr.del_first = 0xffff;
    }
    
    // make up record id
    id = (ridx << 16) + size;
    addr = (pagemgr.record_offset <<16) + size;
    // store record address and size into addr table
    setaddr(ridx, addr);
    // copy record data
    memcpy((void *)(pagemgr.page + pagemgr.record_offset),
        (const void *)r.c_str(), (size_t)size);
    pagemgr.record_offset + size;

    pagemgr.total_size += size;
    num_records++;
    return id;
}

string GetRecord(RecordID id)
{
    int size = id & 0x0000ffff;
    unsigned short ridx = (id >> 16);
    unsigned short offset = (unsigned short)(getaddr(ridx)>>16);

    if (offset < 0 ||
        offset > PAGE_SIZE  ||
        size <= 0 ||
        offset + size > PAGE_SIZE) {
        // invalid id
        return NULL;
    }

    const char *r_start = pagemgr.page + offset;
    string r(r_start, size);
    return r;
}

bool DelRecord(RecordID id)
{
    int size = id & 0x0000ffff;
    unsigned short ridx = (id >> 16);
    unsigned short offset = (unsigned short)(getaddr(ridx)>>16);

    if (!pagemgr.num_records) return false;
    if (offset < 0 ||
        offset > PAGE_SIZE  ||
        size <= 0 ||
        offset + size > PAGE_SIZE) {
        // invalid id
        return false;
    }

    if (ridx + 1 == pagemgr.addr_offset/4) {
        // if record with largest idx is deleted
        // reduce entire address range
        pagemgr.addr_offset -= 4;
    } else {
        setaddr(ridx, (pagemgr.del_first | (1<<31)));
        pagemgr.del_first = ridx;
    }

    pagemgr.total_size -= size;
    pagemgr.num_records--;
    return true;
}
